package ljl.alg.jianzhioffer.round2;

import commons.TreeNode;

/**
 * 这道题做了得五六次了
 * 没有一次是能做出来的
 *
 * 虽然是简单题，并不简单
 * */
public class _68_2_lowest_common_ancestor {
    
    /**
     * 递归
     * 退出条件：root 等于 p 或 q 或 null
     * 过程：分别以 root 的 left 和 right 为参数调用函数，返回记为 left 和 right
     * 返回：left right 均为 null：说明两个孩子都不在 root 下，返回 null
     * 仅 left null：说明两个孩子在 right
     * 仅 right null：说明在 left
     * 都不是 null：返回 root
     *
     * */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q)
            return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
}
